/**
 * 204. 计数质数
 * https://leetcode-cn.com/problems/count-primes/
 */
public class Solutions_204 {
    public static void main(String[] args) {
//        int n = 10;  // output: 4  {2, 3, 5, 7}
//        int n = 0;  // output: 0
//        int n = 1;  // output: 0
//        int n = 10000;  // output: 1229
        int n = 499979;  // output: 41537

        int result = countPrimes(n);
        System.out.println(result);
    }

    /**
     * 解法二：埃氏筛（厄拉多塞筛法）（13ms）
     */
    public static int countPrimes(int n) {
        int res = 0;
        // mark[2] = false，表示 2 是一个质数
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i ++) {
            if (!isPrime[i]) {
                res ++;
                if ((long) i * i >= n) {
                    // 防止乘积大于 Integer.MAX_VALUE，而溢出
                    continue;
                }
                // 如果 x 是质数，那么大于 x 的 x 的倍数 2x, 3x, ...一定不是质数
                // 为什么要从 i * i 开始标记，而不是 2 * i 呢？
                // 因为 i 等于 2，3，5 较小的质数时，已经把倍数给标记过了
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        return res;
    }

    /**
     * 解法一：枚举法（超时）
     */
    public static int countPrimes2(int n) {
        int res = 0;
        for (int i = 2; i < n; i++) {
            res += isPrime(i) ? 1 : 0;
        }
        return res;
    }

    /**
     * 判断 n 是否是质数：只能被 1 和自身整除的数
     */
    public static boolean isPrime(int n) {
        // 仅将 i 遍历到 Math.sqrt(n)，而不是 n
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        // n 不能被 [2, Math.sqrt(n)] 中的元素整除，那么 n 一定是质数
        return true;
    }
}
